package ACWing._849_Dijkstra求最短路1;

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] g = new int[n+1][n+1];
        for (int i = 0; i < m; i++) {
            int s = scanner.nextInt();
            int e = scanner.nextInt();
            int w = scanner.nextInt();
            g[s][e] = g[s][e]==0? w: Math.min(g[s][e],w);
        }

        int[] dist = new int[n+1];
        boolean[] visited = new boolean[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[1] = 0;

        for (int i = 0; i < n - 1; i++) {
            System.out.println(Arrays.toString(dist));
            int t = -1;
            for(int j=1;j<=n;j++){
                if(!visited[j] && (t==-1||dist[t]>dist[j])){
                    t = j;
                }
            }
            // 更新与t相邻其他点
            for (int j = 1; j <=n ; j++) {
                if(g[t][j]>0)
                    dist[j] = Math.min(dist[j], dist[t]+g[t][j]);
            }
            visited[t] = true;
        }
        if(dist[n]==Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(dist[n]);

        scanner.close();
    }
}
